import java.util.Comparator;
import java.util.PriorityQueue;

public class Test2 {

    //最小花费
    public static int pileStones1(int a[]){
        PriorityQueue<Integer> integers = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        int sumMoney = 0;
        //1.入队
        for(int i = 0;i < a.length;i++){
            integers.offer(a[i]);
        }
        //2.出队
        while(!integers.isEmpty()){
            int num1 = integers.poll();
            if(integers.isEmpty()){
                return sumMoney;
            }
            int num2 = integers.poll();
            sumMoney += (num1 + num2);
            integers.offer(num1 + num2);
        }
        return sumMoney;

    }

    //最大花费
    public static int pileStones2(int a[]){
        PriorityQueue<Integer> integers = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int sumMoney = 0;
        //1.入队
        for(int i = 0;i < a.length;i++){
            integers.offer(a[i]);
        }
        //2.出队
        while(!integers.isEmpty()){
            int num1 = integers.poll();
            if(integers.isEmpty()){
                return sumMoney;
            }
            int num2 = integers.poll();
            sumMoney += (num1 + num2);
            integers.offer(num1 + num2);
        }
        return sumMoney;

    }

    public static void main(String[] args) {
        int a[] = {45, 13, 12, 16, 9, 5, 22};
        System.out.println("合并石子的最小花费是："+pileStones1(a));
        System.out.println("合并石子的最大花费是："+pileStones2(a));
    }

}
